// https://leetcode.cn/problems/3sum-with-multiplicity/description/


func threeSumMulti(arr []int, target int) int {
    ans := 0
	mod := 1000000007
	for i := 0; i < len(arr); i++ {
		remain := target - arr[i]
		rec := make(map[int]int)
		for j := i + 1; j < len(arr); j++ {
			if v, e := rec[arr[j]]; e {
				ans += v
			}
			rec[remain - arr[j]]++
		}
	}
	return ans % mod
}